package leet;

import java.util.HashMap;

/**
 * Given an array of integers and an integer k, you need to find the total
 * number of continuous subarrays whose sum equals to k.
 */
public class Leet0560 {

	public static void main(String[] args) {
		Leet0560 leet560 = new Leet0560();

		int[] nums = { -1, -1, 1 };
		int k = 0;
		int subarraySum = leet560.subarraySum(nums, k);

		System.out.println(subarraySum);
	}

	/**
	 * 
	 * 这个就比较6了。 sum(i,j)=sum(0,j)-sum(0,i)
	 * 
	 * map cache sum(0,i)的值 和 次数
	 * 
	 * @param nums
	 * @param k
	 * @return
	 * @date 2019年4月16日
	 */
	private int subarraySum(int[] nums, int k) {

		if (nums.length == 1) {
			return nums[0] == k ? 1 : 0;
		}

		int count = 0;

		// TODO 这两个循环可以放一个里其实
		for (int i = 1; i < nums.length; i++) {
			nums[i] += nums[i - 1];
		}

		HashMap<Integer, Integer> map = new HashMap<>();

		for (int num : nums) {

			if (k == num) {
				count++;
			}

			// map中存的是之前的sum(0,i)
			if (map.containsKey(num - k)) {
				count += map.get(num - k);
			}
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
		return count;
	}

	/**
	 * 第一步： 1 2 1 3 2 1
	 * 
	 * 用一个一维数组，计算的时候比较 1 0 0 2 1 0 3 2 1
	 * 
	 * 本质：二重循环
	 * 
	 * 另外,其实用一个sum就可以计算，只不过用数组做cache快一点点
	 * 
	 * @param nums
	 * @param k
	 * @return
	 * @date 2019年4月16日
	 */
	public int subarraySum0(int[] nums, int k) {
		int count = 0;
		int n = nums.length;
		int[] r = new int[n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				r[j] = r[j] + nums[i];
				if (r[j] == k) {
					count++;
				}
			}
		}

		return count;
	}
}
